package com.cuz.hot100;

public class Q89largestRectangleArea {
    public static void main(String[] args) {
//        int[] ints = {2, 1, 5, 6, 2, 3};
        int[] ints = {1, 1};
        System.out.println(largestRectangleArea1(ints));
    }

    public static int largestRectangleArea1(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int length = heights.length;
        int[] leftMin = new int[length];
        int[] rightMin = new int[length];
        leftMin[0] = -1;
        rightMin[length - 1] = length;
        for (int i = 1; i < leftMin.length; i++) {
            int preValue = heights[i - 1];
            int leftMinIndex = leftMin[i - 1];
            if (preValue <= heights[i]) {
                leftMin[i] = i - 1;
                continue;
            }
            if (leftMinIndex >= 0 && heights[leftMinIndex] <= heights[i]) {
                leftMin[i] = leftMinIndex;
                continue;
            }
            leftMin[i] = i;
        }
        for (int i = length - 2; i >= 0; i--) {
            int preValue = heights[i + 1];
            int rightMinIndex = rightMin[i + 1];
            if (preValue <= heights[i]) {
                rightMin[i] = i + 1;
                continue;
            }
            if (rightMinIndex < length && heights[rightMinIndex] <= heights[i]) {
                rightMin[i] = rightMinIndex;
                continue;
            }
            rightMin[i] = i;
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            int left = leftMin[i];
            int right = rightMin[i];
            int dis = right - left - 1;
            ans = Math.max(dis * heights[i], ans);
        }
        return ans;
    }
}
